// https://www.lintcode.com/problem/search-a-2d-matrix/

public class Solution {
    /**
     * @param matrix: matrix, a list of lists of integers
     * @param target: An integer
     * @return: a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if (matrix.length == 0) {
            return false;
        }
        int rows = matrix.length, cols = matrix[0].length;
        if ((target < matrix[0][0]) || (target > matrix[rows - 1][cols - 1])) {
            return false;
        }
        int start_row = 0, end_row = rows, row = 0;
        while (start_row < end_row) { 
            row = (start_row + end_row) / 2;
            if (matrix[row][0] < target) {
                start_row = row + 1;
            }
            else if (matrix[row][0] > target) {
                end_row = row; // 开区间，不用减1处理。
            }
            else {
                break; // 定位到可能在的那一，继续二分。
            }
        }
        // 检查数据
        if (matrix[row][0] > target) {
            row -= 1;
        }
        int start_col = 0, end_col = cols, col = 0;
        while (start_col < end_col) {
            col = (start_col + end_col) / 2;
            if (matrix[row][col] < target) {
                start_col = col + 1;
            }
            else if (matrix[row][col] > target) {
                end_col = col;
            }
            else {
                return true;
            }
        }
        return false;
    }
}